﻿\subsection{Массив указателей на строки}
\label{array_of_pointers_to_strings}

Вот пример массива указателей.

\lstinputlisting[caption=Получить имя месяца,label=get_month1,style=customc]{patterns/13_arrays/45_month_1D/month1_RU.c}

\subsubsection{x64}

\lstinputlisting[caption=\Optimizing MSVC 2013 x64,style=customasmx86]{patterns/13_arrays/45_month_1D/month1_MSVC_2013_x64_Ox.asm}

Код очень простой:

\begin{itemize}

\item
\myindex{x86!\Instructions!MOVSXD}
Первая инструкция \INS{MOVSXD} копирует 32-битное значение из \ECX (где передается аргумент $month$)
в \RAX со знаковым расширением (потому что аргумент $month$ имеет тип \Tint).

Причина расширения в том, что это значение будет использоваться в вычислениях наряду с другими 64-битными
значениями.

Таким образом, оно должно быть расширено до 64-битного
\footnote{Это немного странная вещь, но отрицательный индекс массива может быть передан как $month$ 
(отрицательные индексы массивов будут рассмотрены позже: \myref{negative_array_indices}).
И если так будет, отрицательное значение типа \Tint будет расширено со знаком корректно
и соответствующий элемент перед таблицей будет выбран.
Всё это не будет корректно работать без знакового расширения.}.

\item
Затем адрес таблицы указателей загружается в \RCX.

\item
В конце концов, входное значение ($month$) умножается на 8 и прибавляется к адресу.
Действительно: мы в 64-битной среде и все адреса (или указатели) 
требуют для хранения именно 64 бита (или 8 байт).
Следовательно, каждый элемент таблицы имеет ширину в 8 байт.
Вот почему для выбора элемента под нужным номером нужно пропустить $month*8$ байт от начала.
Это то, что делает \MOV.
Эта инструкция также загружает элемент по этому адресу.
Для 1, элемент будет указателем на строку, содержащую \q{February}, итд.

\end{itemize}

\Optimizing GCC 4.9 может это сделать даже лучше
\footnote{В листинге осталось \q{0+}, потому что вывод ассемблера GCC не так скрупулёзен, чтобы убрать это.
Это \IT{displacement} и он здесь нулевой.}:

\begin{lstlisting}[caption=\Optimizing GCC 4.9 x64,style=customasmx86]
	movsx	rdi, edi
	mov	rax, QWORD PTR month1[0+rdi*8]
	ret
\end{lstlisting}

\myparagraph{32-bit MSVC}

Скомпилируем также в 32-битном компиляторе MSVC:

\lstinputlisting[caption=\Optimizing MSVC 2013 x86,style=customasmx86]{patterns/13_arrays/45_month_1D/month1_MSVC_2013_x86_Ox.asm}

Входное значение не нужно расширять до 64-битного значения, так что оно используется как есть.

И оно умножается на 4, потому что элементы таблицы имеют ширину 32 бита или 4 байта.

% FIXME1 move to another file
\subsubsection{32-битный ARM}

\myparagraph{ARM в режиме ARM}

\lstinputlisting[caption=\OptimizingKeilVI (\ARMMode),style=customasmARM]{patterns/13_arrays/45_month_1D/month1_Keil_ARM_O3.s}

% TODO Fix R1s
Адрес таблицы загружается в R1.

\myindex{ARM!\Instructions!LDR}
Всё остальное делается, используя только одну инструкцию \LDR.

Входное значение $month$ сдвигается влево на 2 (что тоже самое что и умножение на 4), это значение
прибавляется к R1 (где находится адрес таблицы) и затем элемент таблицы загружается по этому адресу.

32-битный элемент таблицы загружается в R0 из таблицы.

\myparagraph{ARM в режиме Thumb}

Код почти такой же, только менее плотный, потому что здесь, в инструкции \LDR, нельзя задать суффикс \LSL:

\begin{lstlisting}[style=customasmARM]
get_month1 PROC
        LSLS     r0,r0,#2
        LDR      r1,|L0.64|
        LDR      r0,[r1,r0]
        BX       lr
        ENDP
\end{lstlisting}

\subsubsection{ARM64}

\lstinputlisting[caption=\Optimizing GCC 4.9 ARM64,style=customasmARM]{patterns/13_arrays/45_month_1D/month1_GCC49_ARM64_O3.s}

\myindex{ARM!\Instructions!ADRP/ADD pair}
Адрес таблицы загружается в X1 используя пару \ADRP/\ADD.

Соответствующий элемент выбирается используя одну инструкцию \LDR, которая берет W0
(регистр, где находится значение входного аргумента $month$), сдвигает его на 3 бита влево
(что то же самое что и умножение на 8),
расширяет его, учитывая знак (это то, что означает суффикс \q{sxtw}) и прибавляет к X0.

Затем 64-битное значение загружается из таблицы в X0.

\subsubsection{MIPS}

\lstinputlisting[caption=\Optimizing GCC 4.4.5 (IDA),style=customasmMIPS]{patterns/13_arrays/45_month_1D/MIPS_O3_IDA_RU.lst}

\subsubsection{Переполнение массива}

Наша функция принимает значения в пределах 0..11, но что будет, если будет передано 12?

В таблице в этом месте нет элемента.
Так что функция загрузит какое-то значение, которое волею случая находится там, и вернет его.

Позже, какая-то другая функция попытается прочитать текстовую строку по этому адресу и, возможно, упадет.

Скомпилируем этот пример в MSVC для win64 и откроем его в \IDA чтобы посмотреть, что линкер расположил
после таблицы:

\lstinputlisting[caption=Исполняемый файл в IDA,style=customasmx86]{patterns/13_arrays/45_month_1D/MSVC2012_win64_1.lst}

Имена месяцев идут сразу после.
Наша программа все-таки крошечная,
так что здесь не так уж много данных (всего лишь названия месяцев) для расположения их в сегменте данных.

Но нужно заметить, что там может быть действительно \IT{что угодно}, что линкер решит там расположить, случайным образом.%

Так что будет если 12 будет передано в функцию?
Вернется 13-й элемент таблицы.
Посмотрим, как CPU обходится с байтами как с 64-битным значением:

\lstinputlisting[caption=Исполняемый файл в IDA,style=customasmx86]{patterns/13_arrays/45_month_1D/MSVC2012_win64_2.lst}

И это 0x797261756E614A.
После этого, какая-то другая функция (вероятно, работающая со строками) попытается загружать байты
по этому адресу, ожидая найти там Си-строку.

И скорее всего упадет, потому что это значение не выглядит как действительный адрес.

\myparagraph{Защита от переполнения массива}

\epigraph{Если какая-нибудь неприятность может случиться, она случается}{Закон Мерфи}

Немного наивно ожидать что всякий программист, кто будет использовать вашу функцию или библиотеку,
никогда не передаст аргумент больше 11.

Существует также хорошая философия \q{fail early and fail loudly} или \q{fail-fast},
которая учит сообщать об ошибках как можно раньше и останавливаться.

\myindex{\CStandardLibrary!assert()}
Один из таких методов в \CCpp это макрос assert().

Мы можем немного изменить нашу программу, чтобы она падала при передаче неверного значения:

\lstinputlisting[caption=assert() добавлен,style=customc]{patterns/13_arrays/45_month_1D/month1_assert.c}

Макрос будет проверять на верные значения во время каждого старта функции и падать если выражение возвращает false.

\lstinputlisting[caption=\Optimizing MSVC 2013 x64,style=customasmx86]{patterns/13_arrays/45_month_1D/MSVC2013_x64_Ox_checked.asm}

На самом деле, assert() это не функция, а макрос. Он проверяет условие и передает также номер строки и название
файла в другую функцию, которая покажет эту информацию пользователю.

Мы видим, что здесь и имя файла и выражение закодировано в UTF-16.

Номер строки также передается (это 29).

Этот механизм, пожалуй, одинаковый во всех компиляторах.

Вот что делает GCC:

\lstinputlisting[caption=\Optimizing GCC 4.9 x64,style=customasmx86]{patterns/13_arrays/45_month_1D/GCC491_x64_O3_checked.s}

Так что макрос в GCC также передает и имя функции, для удобства.

Ничего не бывает бесплатным и проверки на корректность тоже.

Это может замедлить работу вашей программы, особенно если макрос assert() используется в маленькой
критичной ко времени функции.

Так что, например, MSVC оставляет проверки в отладочных сборках, но в окончательных сборках они исчезают.
 
Ядра Microsoft \gls{Windows NT} также идут в виде сборок \q{checked} и \q{free}
\footnote{\href{http://go.yurichev.com/17259}{msdn.microsoft.com/en-us/library/windows/hardware/ff543450(v=vs.85).aspx}}.
В первых есть проверки на корректность аргументов (отсюда \q{checked}), а во вторых~--- нет (отсюда \q{free},
т.е.~\q{свободные} от проверок).

Разумеется, \q{checked}-ядро работает медленнее из-за всех этих проверок, поэтому его обычно используют только на время отладки драйверов, либо самого ядра.

% FIXME: ARM? MIPS?
